Nondeterministic Pushdown Automata

Nondeterministic Pushdown Automata

• 自動機 長相

  
  

  • 最初的stack

• 下推自動機的定義

  

• 轉移函數的定義

  

  • 邊上的定義

    
    

    • 也可以推string
  • Example

    

  • Stack是空的 不允許任何轉移

    

• Non-determinism

  

• 什麼樣的string是被accept的

  

  • 一個例子

    

• 如何描述狀態機

  
  

  • 轉移

    

  • 完整過程

• 正式定義

  

• Example

  • a的數量跟 b的一樣

    

• 什麼樣的string不被接受

  
  

Pushdown Automata and Context-Free Languages

• 被NPDA接受的語言 相當於CFG

  

• step 1: 證明 CFG 屬於被NPDA接受的語言

  

  • 方法

    
    
    

  • 以例子簡單說明

    
    

  • 因此

    

• step 2: 證明 被NPDA接受的語言 屬於CFG

  

  • grammar本質上是機器的狀態移動
  • 前置需求

    
    

    • 清空Stack

      

    • 任何移動 要嘛減少或增加stack content
    • 作法

      
      
      

  • 實際作法省略 …

Deterministic Pushdown Automata and Deterministic CFLs

• 接受的轉移

  
  

• 不接受的轉移

  

• PDA

  
  

  • Example

    
    

• 定義 一個語言是deterministic context-free

  

• NPDA 比 DPA更加強大

  
  

• 證明

  

  • 例子

    
    
    
    

    • 假設存在DPDA接受它

      
      

    • 需要用到一些fact 先來講fact…

• fact

  
  
  

• 繼續證明

  
  
  

  • 產生矛盾